package simple.array;

/**
 * <a href="https://leetcode-cn.com/problems/replace-elements-with-greatest-element-on-right-side>1299. 将每个元素替换为右侧最大元素</a>
 * 给你一个数组arr，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1替换。
 * 完成所有替换操作后，请你返回这个数组。
 * 示例 1：
 *   输入：arr = [17,18,5,4,6,1]
 *   输出：[18,6,6,6,1,-1]
 * 解释：
 * - 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
 * - 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
 * - 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
 * - 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
 * - 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
 * - 下标 5 的元素 --> 右侧没有其他元素，替换为 -1
 * 示例 2：
 *   输入：arr = [400]
 *   输出：[-1]
 *   解释：下标 0 的元素右侧没有其他元素。
 * 提示：
 *   1 <= arr.length <= 104
 *   1 <= arr[i] <= 105
 * 解题思路：
 *   1.从右往左遍历数组
 *   2.记录当前元素，并且将当前位置上的元素替换为最大值（初始值为-1）
 *   3.若当前元素大于最大值，则更新最大值为当前元素
 * @author 刘学松
 * @date 2021/3/8 20:11
 */
public class 将每个元素替换为右侧最大元素 {
    public static int[] replaceElements(int[] arr) {
        int length = arr.length;

        int max = -1;
        int temp;
        for (int i = length-1; i >= 0; i--) {
            temp = arr[i];
            arr[i] = max;
            if (temp > max) {
                max = temp;
            }
        }

        return arr;
    }
}
